package org.example.dfs;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.List;

/**
 * @author liyishan
 * @date 2023/9/4 09:59
 * @apiNote
 */

public class Test00089GrayCode {

    public static void main(String[] args) {
        List<Integer> res= test2(2);
        System.out.println(JSON.toJSON(res));
    }

    public static List<Integer> test(int n) {
        List<Integer> res = new ArrayList<>();
        res.add(0);
        for(int i = 1;i<=n;i++){
            int m = res.size();
            for(int j = m-1;j>=0;j--){
                res.add(res.get(j) | (1 << (i-1)));
            }
        }
        return res;
    }

    public static List<Integer> test1(int n) {
        List<Integer> res = new ArrayList<>();
        res.add(0);
        for(int i = 1;i<1<<n;i++){
            res.add((i>>1) ^ i);
        }
        return res;
    }

    public static List<Integer> test2(int n){
        List<Integer> res= new ArrayList<>();
        dfs(res,0,0,0,n);
        return res;
    }

    public static void dfs(List<Integer> res,int node,int isRightSubtree,int deepth,int n){
        if(deepth == n){
            res.add(node);
            return;
        }
        dfs(res,(node<<1)| isRightSubtree,0,deepth+1,n);
        dfs(res,(node<<1)| isRightSubtree^1,1,deepth+1,n);
    }
}
